class Solution {  //二分查找算法（二段性，<=、>) 
public:   //算术平方根 = 根号X,在[1, x]区间内找出某个数的平方<x(它的后一个数平方>x),或者=x
    int mySqrt(int x) {
        int left = 1, right = x; 
        while(left < right)  //循环条件
        {   //数据会溢出, mid*mid, int(2^31-1) -> long long(2^63-1)
            long long mid = left + (right - left + 1) / 2;  //中间点的选择(后面有-1,前面就有+1)
            if(mid * mid <= x) left = mid;  //是平方
            else right = mid - 1;
        }
        return right;  //x=0,边界情况
    } //从0开时查找，得不到正确结果
};